import java.util.Arrays;

/**
 * @author LKQ
 * @date 2022/1/7 19:59
 * @description 动态规划-最高有效位
 */
public class FormalSolution1 {
    public static void main(String[] args) {
        FormalSolution1 formalSolution1 = new FormalSolution1();
        System.out.println(Arrays.toString(formalSolution1.countBits(10)));
    }

    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; i++) {
            if ((i & (i - 1)) == 0) {
                // 判断i是否为2的幂, highBit为最高有效位
                highBit = i;
            }
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }
}
